<!DOCTYPE html>
            
<HTML>
<HEAD>
<meta name="booktitle" content="Developing Applications With Objective Caml" >
 <meta charset="ISO-8859-1"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<META name="GENERATOR" content="hevea 1.05-7 of 2000-02-24">
<META NAME="Author" CONTENT="Christian.Queinnec@lip6.fr">
<LINK rel=stylesheet type="text/css" href="videoc-ocda.css">
<script language="JavaScript" src="videoc.js"><!--
//--></script>
<TITLE>
 Concurrent Processes
</TITLE>
</HEAD>
<BODY class="regularBody">
<A HREF="book-ora174.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora176.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2> Concurrent Processes</H2>
<A NAME="@concepts347"></A>
<A NAME="@concepts348"></A>
<A NAME="@concepts349"></A>With an application composed of many concurrent processes, we lose
the convenience offered by the determinism of sequential programs.
For processes sharing the same zone of memory, the result of the
following program cannot be deduced from reading it.<BR>
<BR>
<DIV ALIGN=center>
<TABLE BORDER=1 CELLSPACING=0 CELLPADDING=1>
<TR><TD  ALIGN=center NOWRAP>main program</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP><B>let</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>1</CODE>;;</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP><TABLE BORDER=1 CELLSPACING=0 CELLPADDING=1>
<TR><TD  ALIGN=left NOWRAP>process <I>P</I></TD>
<TD  ALIGN=left NOWRAP>process <I>Q</I></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>x<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>!</CODE>x<CODE> </CODE><CODE>+</CODE><CODE> </CODE><CODE>1</CODE>;;</TD>
<TD  ALIGN=left NOWRAP>x<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>!</CODE>x<CODE> </CODE><CODE>*</CODE><CODE> </CODE><CODE>2</CODE>;;</TD>
</TR></TABLE></TD>
</TR></TABLE>
</DIV>
At the end of the execution of <I>P</I> and <I>Q</I>, the reference <TT>x</TT>
can point to 2, 3 or 4, depending on the order of execution of each
process.<BR>
<BR>
This indeterminism applies also to terminations. When the memory
state depends on the execution of each parallel process, an
application can fail to terminate on a particular execution, and
terminate on another. To provide some control over the execution, the
processes must be synchronized.<BR>
<BR>
For processes using distinct memory areas, but communicating between
each other, their interaction depends on the type of
communication. We introduce for the following example two
communication primitives: <TT>send</TT> which sends a value,
showing the destination, and <TT>receive</TT> which receives a
value from a process. Let <I>P</I> and <I>Q</I> be two communicating
processes:
<DIV ALIGN=center>
<A NAME="tab-proc-com"></A>
<TABLE BORDER=1 CELLSPACING=0 CELLPADDING=1>
<TR><TD  ALIGN=left NOWRAP>process <I>P</I></TD>
<TD  ALIGN=left NOWRAP>process <I>Q</I></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><B>let</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>1</CODE>;;</TD>
<TD  ALIGN=left NOWRAP><B>let</B><CODE> </CODE>y<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>1</CODE>;;</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>send<TT>(</TT>Q<CODE>,!</CODE>x<TT>)</TT>;</TD>
<TD  ALIGN=left NOWRAP>y<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>!</CODE>y<CODE> </CODE><CODE>+</CODE><CODE> </CODE><CODE>3</CODE>;</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>x<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>!</CODE>x<CODE> </CODE><CODE>*</CODE><CODE> </CODE><CODE>2</CODE>;</TD>
<TD  ALIGN=left NOWRAP>y<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>!</CODE>y<CODE> </CODE><CODE>+</CODE><CODE> </CODE>receive<TT>(</TT>P<TT>)</TT>;</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>send<TT>(</TT>Q<CODE>,!</CODE>x<TT>)</TT>;</TD>
<TD  ALIGN=left NOWRAP>send<TT>(</TT>P<CODE>,!</CODE>y<TT>)</TT>;</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>x<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>!</CODE>x<CODE> </CODE><CODE>+</CODE><CODE> </CODE>receive<TT>(</TT>Q<TT>)</TT>;</TD>
<TD  ALIGN=left NOWRAP>y<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>!</CODE>y<CODE> </CODE><CODE>+</CODE><CODE> </CODE>receive<TT>(</TT>P<TT>)</TT>;</TD>
</TR></TABLE>
</DIV>
In the case of a transient communication, process <I>Q</I> can miss
the messages of <I>P</I>. We fall back into the non-determinism of the
preceding model.<BR>
<BR>
For an asynchronous communication, the medium of the communication
channel stores the different values that have been transmitted. Only
reception is blocking. Process <I>P</I> can be waiting for <I>Q</I>, even
if the latter has not yet read the two messages from <I>P</I>. However, this
does not prevent it from transmitting.<BR>
<BR>
We can classify concurrent applications into five categories
according to the program units that compose them:
<OL type=1>
<LI>
 unrelated; 

<LI> related, but without synchronization;

<LI> related, with mutual exclusion;

<LI> related, with mutual exclusion and communication;

<LI> related, without mutual exclusion, and with synchronous communication.
</OL>The difficulty of implementation comes principally from these last
categories. Now we will see how to resolve these difficulties by
using the Objective CAML libraries.<BR>
<BR>
<A NAME="toc257"></A>
<H3> Compilation with Threads</H3>
The Objective CAML thread library is divided into five modules, of which the
first four each define an abstract type:
<UL>
<LI>
 module <TT>Thread</TT>: creation and execution of threads. 
 (type <I>Thread.t</I>);

<LI> module <TT>Mutex</TT>: creation, locking and release of mutexes. 
 (type <I>Mutex.t</I>);

<LI> module <TT>Condition</TT>: creation of conditions (signals), 
waiting and waking up on a condition (type <I>Condition.t</I>);

<LI> module <TT>Event</TT>: creation of communication channels
 (type <I>'a Event.channel</I>), the values which they carry 
 (type <I>'a Event.event</I>), and communication functions.

<LI> module <TT>ThreadUnix</TT>: redefinitions of I/O functions 
 of module <TT>Unix</TT> so that they are not blocking.
</UL>This library is not part of the execution library of Objective CAML. Its
use requires the option <TT>-custom</TT> both for compiling
programs and for constructing a new toplevel by using
the commands:
<PRE>
$ ocamlc -thread -custom threads.cma  files.ml -cclib -lthreads
$ ocamlmktop -tread -custom -o threadtop thread.cma -cclib -lthreads
</PRE>The <TT>Threads</TT> library is not usable with the native compiler
unless the platform implements threads conforming to the POSIX
1003<A NAME="text45" HREF="book-ora182.html#note45"><SUP><FONT SIZE=2>1</FONT></SUP></A>. Thus we
compile executables by adding the libraries <TT>unix.a</TT> and
<TT>pthread.a</TT>:<BR>
<BR>
<PRE>
$ ocamlc -thread -custom threads.cma files.ml -cclib -lthreads \
  -cclib -lunix -cclib -lpthread
$ ocamltop -thread -custom threads.cma files.ml -cclib -lthreads \
  -cclib -lunix -cclib -lpthread
$ ocamlcopt -thread threads.cmxa files.ml -cclib -lthreads \
  -cclib -lunix -cclib -lpthread
</PRE><A NAME="toc258"></A>
<H3> Module <TT>Thread</TT></H3>
<A NAME="@fonctions442"></A>
The Objective CAML <TT>Thread</TT> module contains the primitives for
creation and management of threads. We will not make an exhaustive
presentation, for instance the operations of file I/O have been
described in the preceding chapter.<BR>
<BR>
<A NAME="@concepts350"></A>
A thread is created through a call to:
<A NAME="@fonctions443"></A>


<PRE><BR># Thread.create<CODE> </CODE>;;<BR><CODE>- : ('a -&gt; 'b) -&gt; 'a -&gt; Thread.t = &lt;fun&gt;</CODE><BR>

</PRE>

The first argument, of type <I>'a -&gt; 'b</I>, corresponds to the
function executed by the created process; the second argument, of type
<I>'a</I>, is the argument required by the executed function; the
result of the call is the descriptor associated with the process. The
process thus created is automatically destroyed when the associated
function terminates.<BR>
<BR>
Knowing its descriptor, we can ask for the execution of a process and
wait for it to finish by using the function
<TT>join</TT>. Here is a usage example:


<PRE><BR># <B>let</B><CODE> </CODE>f_proc1<CODE> </CODE>()<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>for</B><CODE> </CODE>i<CODE>=</CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE><CODE>1</CODE><CODE>0</CODE><CODE> </CODE><B>do</B><CODE> </CODE>Printf.printf<CODE> </CODE><CODE>"(%d)"</CODE><CODE> </CODE>i;<CODE> </CODE>flush<CODE> </CODE>stdout<CODE> </CODE><B>done</B>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_newline()<CODE> </CODE>;;<BR><CODE>val f_proc1 : unit -&gt; unit = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>t1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Thread.create<CODE> </CODE>f_proc1<CODE> </CODE>()<CODE> </CODE>;;<BR><CODE>val t1 : Thread.t = &lt;abstr&gt;</CODE><BR># Thread.join<CODE> </CODE>t1<CODE> </CODE>;;<BR><CODE>(0)(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)</CODE><BR><CODE>- : unit = &lt;unknown constructor&gt;</CODE><BR>

</PRE>
<BR>
<BR>


<H3> Warning </H3> <HR>

The result of the execution of a process is not recovered by the
parent process, but lost when the child process terminates.


<HR>

<BR>
<BR>
<A NAME="@fonctions444"></A>
We can also brutally interrupt the execution of a process of which
we know the descriptor with the function
<TT>kill</TT>. For instance, we create a process which is immediately interrupted:


<PRE><BR># <B>let</B><CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>0</CODE><CODE> </CODE>;;<BR><CODE>val n : int ref = {contents=0}</CODE><BR># <B>let</B><CODE> </CODE>f_proc1<CODE> </CODE>()<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>while</B><CODE> </CODE><B>true</B><CODE> </CODE><B>do</B><CODE> </CODE>incr<CODE> </CODE>n<CODE> </CODE><B>done</B><CODE> </CODE>;;<BR><CODE>val f_proc1 : unit -&gt; unit = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>go<CODE> </CODE>()<CODE> </CODE><CODE>=</CODE><CODE> </CODE>n<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>t1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Thread.create<CODE> </CODE>f_proc1<CODE> </CODE>()<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>Thread.kill<CODE> </CODE>t1<CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Printf.printf<CODE> </CODE><CODE>"n = %d\n"</CODE><CODE> </CODE><CODE>!</CODE>n<CODE> </CODE>;;<BR><CODE>val go : unit -&gt; unit = &lt;fun&gt;</CODE><BR># go<CODE> </CODE>()<CODE> </CODE>;;<BR><CODE>n = 0</CODE><BR><CODE>- : unit = ()</CODE><BR>

</PRE>
<BR>
<BR>
A process can put an end to its own activity by the function:
<A NAME="@fonctions445"></A>


<PRE><BR># Thread.exit<CODE> </CODE>;;<BR><CODE>- : unit -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
It can suspend its activity for a given time by a call to:
<A NAME="@fonctions446"></A>


<PRE><BR># Thread.delay<CODE> </CODE>;;<BR><CODE>- : float -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The argument stands for the number of seconds to wait.<BR>
<BR>
Let us consider the previous example, and add timing. We create a
first process
<TT>t1</TT> of which the associated function 
<TT>f_proc2</TT> creates in its turn a process <TT>t2</TT> which executes
 <TT>f_proc1</TT>, then <TT>f_proc2</TT> delays for 
<TT>d</TT> seconds, and then terminates <TT>t2</TT>. On termination of
<TT>t1</TT>, we print the contents of <TT>n</TT>.


<PRE><BR># <B>let</B><CODE> </CODE>f_proc2<CODE> </CODE>d<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>n<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>t2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Thread.create<CODE> </CODE>f_proc1<CODE> </CODE>()<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>Thread.delay<CODE> </CODE>d<CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Thread.kill<CODE> </CODE>t2<CODE> </CODE>;;<BR><CODE>val f_proc2 : float -&gt; unit = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>t1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Thread.create<CODE> </CODE>f_proc2<CODE> </CODE><CODE>0</CODE><CODE>.</CODE><CODE>2</CODE><CODE>5</CODE><CODE> </CODE><BR><CODE> </CODE><B>in</B><CODE> </CODE>Thread.join<CODE> </CODE>t1<CODE> </CODE>;<CODE> </CODE>Printf.printf<CODE> </CODE><CODE>"n = %d\n"</CODE><CODE> </CODE><CODE>!</CODE>n<CODE> </CODE>;;<BR><CODE>n = 128827</CODE><BR><CODE>- : unit = ()</CODE><BR>

</PRE>
<BR>
<BR>
<HR>
<A HREF="book-ora174.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora176.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
